package com.mid;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

/**
 * Created by Lxk on 2019/2/17.
 */
public class CombanitioSum39 {

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        for(int i = 0;i < candidates.length/2; i++){
            int temp = candidates[i];
            candidates[i] = candidates[candidates.length-1-i];
            candidates[candidates.length-1-i] = temp;
        }
        List<List<Integer>> res = new ArrayList<>();
        deepSearch(candidates,target,res);
        return res;
    }

    List<Integer> currentList = new ArrayList<>();

    void deepSearch(int[] candidates, int remainTarget,
                       List<List<Integer>> res){
        if(remainTarget==0){
            List<Integer> copy = new ArrayList<>(currentList);
            Collections.sort(copy);
            for(List<Integer> list : res){
                boolean flag = true;
                for(int i=0;i < copy.size(); i++){
                    if(!copy.get(i).equals(list.get(i))){
                        flag = false;
                        break;
                    }
                }
                if(flag){
                    return ;
                }
            }
            res.add(copy);
            return ;
        }else{
            for(int candidate : candidates){
                if(candidate > remainTarget){
                    continue;
                }
                currentList.add(candidate);
                remainTarget -= candidate;
                deepSearch(candidates,remainTarget,res);
                currentList.remove(currentList.size()-1);
                remainTarget += candidate;
            }
        }
    }

    public static void main(String[] args){
        CombanitioSum39 test = new CombanitioSum39();
        int[] arr = {2,3,6,7};
        List<List<Integer>> res = test.combinationSum(arr,7);
        for(List<Integer> list : res){
            System.out.println(list);
        }
    }

}
